package leetcode100;

// TODO 栈 [经典] 【-】 有效的括号
// TODO https://leetcode.cn/problems/valid-parentheses/solution/leetcode20-li-yong-stackde-popfang-fa-by-enwb/

import java.util.*;

public class lc100_0020 {

    public boolean isValid(String s) {
        Map<Character, Character> pairs = new HashMap<>();
        pairs.put(')', '(');
        pairs.put(']', '[');
        pairs.put('}', '{');

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }

}